package com.algorithm.greedy;

import java.util.*;

/**
 * 狄克斯特拉算法‌
 * 艾兹格·W·迪科斯彻（Edsger W.Dijkstra）
 * Dijkstra算法是一种用于在带权图中找到单源最短路径的算法。
 * 它属于贪心算法的一种，适用于带权重的图，特别是非负权重。
 * Dijkstra算法的核心思想是维护一个最短路径估计的集合，
 * 并逐步扩展这些路径，直到找到从源点到所有其他顶点的最短路径。
 * @author create by xcb 2025/3/6 下午8:50
 */
public class Dijkstra {

    static class Edge {
        int to, weight;
        Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static int[] dijkstra(int[][] graph, int source) {
        int n = graph.length;
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.weight));
        pq.offer(new Edge(source, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int u = current.to;
            if (visited[u]) {
                continue;
            }

            visited[u] = true;

            for (int v = 0; v < n; v++) {
                // graph[u][v] != 0 表示 u 到 v 有边
                if (graph[u][v] != 0 && !visited[v]) {
                    int newDist = dist[u] + graph[u][v];
                    if (newDist < dist[v]) {
                        dist[v] = newDist;
                        pq.offer(new Edge(v, newDist));
                    }
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
//        int[][] graph = {
//                {0, 7, 9, 0, 0, 14},
//                {7, 0, 10, 15, 0, 0},
//                {9, 10, 0, 11, 0, 2},
//                {0, 15, 11, 0, 6, 0},
//                {0, 0, 0, 6, 0, 9},
//                {14, 0, 2, 0, 9, 0}
//        };

        int[][] graph = {
                {0, 2, 4, 0, 0},
                {2, 0, 1, 7, 0},
                {4, 1, 0, 0, 3},
                {0, 7, 0, 0, 1},
                {0, 0, 3, 1, 0},
        };
        int[] distances = dijkstra(graph, 0);
        System.out.println("Shortest distances from source:");
        for (int i = 0; i < distances.length; i++) {
            System.out.println("Vertex " + i + ": " + distances[i]);
        }
    }


}
